package leetcode.sort;

public class HeapSort extends AbstractSort {
    int heapSize;

    public HeapSort(int[] array) {
        super(array);
    }

    @Override
    protected void sort() {
        heapSize = array.length;
        // 原地建堆
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            shiftDown(i);
        }

        // 交换堆顶元素和数组最后一个元素再恢复堆，如此循环
        while (heapSize > 1) {
            swap(0, --heapSize);
            shiftDown(0);
        }
    }

    /**
     * 自下而上的下溢
     */
    private void shiftDown(int i) {
        int target = array[i];          //准备下溢的元素
        int notLeave = heapSize >> 1;   //非叶子结点的数量
        while (i < notLeave) {          //叶子结点没有下溢的空间
            int childIdx = (i << 1) + 1;
            int child = array[childIdx];
            int rightIdx = childIdx + 1;
            // 选出左右孩子中值较大的那位
            if (rightIdx < heapSize && array[rightIdx] > child) {
                childIdx = rightIdx;
                child = array[childIdx];
            }
            // 如果父节点比孩子结点都大，就不用下溢了
            if (target >= child) break;
            swap(i, childIdx);
            i = childIdx;
        }
    }
}
